/**
 * @param {number[]} big
 * @param {number[]} small
 * @return {number[]}
 */
//双循环
var shortestSeq1 = function (big, small) {
  let res = []
  let obj = {}
  let c = small.length
  let dist = big.length
  small.forEach(item => {
    obj[item] = -1
  })
  for (let i = 0; i < big.length; i++) {
    let tmp_c = c
    let start = (end = -1)
    if (!obj[big[i]]) {
      continue
    }
    for (let j = i; j < big.length; j++) {
      let cur = big[j]
      if (obj[cur] && obj[cur] != i + 1) {
        obj[cur] = i + 1
        tmp_c -= 1
        if (start === -1) {
          start = j
        }
      }
      if (tmp_c === 0) {
        end = j
        if (dist > end - start) {
          res = [start, end]
          dist = end - start
        }
        break
      }
    }
  }
  return res
}
//
var shortestSeq2 = function (big, small) {
  let res = []
  let dist = big.length
  let obj = {}
  let c = (c1 = small.length)
  let arr = []
  const search = function (element, arr) {
    let left = 0
    let right = arr.length - 1

    while (left <= right) {
      const mid = Math.floor((left + right) / 2)

      if (arr[mid] === element) {
        return mid
      } else if (arr[mid] < element) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }

    return left
  }
  small.forEach(item => {
    obj[item] = []
  })
  big.forEach((item, idx) => {
    if (item in obj) {
      let tm_arr = obj[item]
      tm_arr.push(idx)
      if (tm_arr.length === 1) {
        c -= 1
      }
    }
  })
  //表明每一个small都在big中
  if (c === 0) {
    //表明big===small
    if (big.length === small.length) {
      return [0, big.length - 1]
    }
    Object.keys(obj).forEach(item => {
      arr.push(obj[item].shift())
    })
    arr.sort((a, b) => a - b)
    while (true) {
      if (dist > arr[c1 - 1] - arr[0]) {
        res = [arr[0], arr[c1 - 1]]
        dist = arr[c1 - 1] - arr[0]
      }
      if (obj[big[arr[0]]].length === 0) {
        break
      }
      let tmp_arr = obj[big[arr.shift(0)]]
      let tmp = tmp_arr.shift()
      //数组已经有序了，二分查找要插入的位置
      let idx = search(tmp, arr)
      // arr.push(tmp)
      arr.splice(idx, 0, tmp)
    }
  }
  return res
}
//滑动窗口
var shortestSeq = function (big, small) {
  let len = big.length
  let res = []
  let obj = {}
  let diff = small.length
  small.forEach(item => {
    obj[item] = 1
  })
  const checkVal = item => item in obj
  for (let l = 0, r = 0; r < big.length; r++) {
    if (checkVal(big[r]) && --obj[big[r]] >= 0) {
      diff -= 1
    }
    while (diff === 0) {
      if (r - l < len) {
        len = r - l
        res = [l, r]
      }
      if (checkVal(big[l]) && ++obj[big[l]] > 0) {
        diff += 1
      }
      l += 1
    }
  }
  return res
}
let big = [7, 5, 9, 0, 2, 1, 3, 5, 7, 9, 1, 1, 5, 8, 8, 9, 7]
small = [1, 5, 9]
big = [1, 2, 3]
small = [1, 2, 3]
big = [
  842, 336, 777, 112, 789, 801, 922, 874, 634, 121, 390, 614, 179, 565, 740,
  672, 624, 130, 555, 714, 9, 950, 887, 375, 312, 862, 304, 121, 360, 579, 937,
  148, 614, 885, 836, 842, 505, 187, 210, 536, 763, 880, 652, 64, 272, 675, 33,
  341, 101, 673, 995, 485, 16, 434, 540, 284, 567, 821, 994, 174, 634, 597, 919,
  547, 340, 2, 512, 433, 323, 895, 965, 225, 702, 387, 632, 898, 297, 351, 936,
  431, 468, 694, 287, 671, 190, 496, 80, 110, 491, 365, 504, 681, 672, 825, 277,
  138, 778, 851, 732, 176
]
small = [
  950, 885, 702, 101, 312, 652, 555, 936, 842, 33, 634, 851, 174, 210, 287, 672,
  994, 614, 732, 919, 504, 778, 340, 694, 880, 110, 777, 836, 365, 375, 536,
  547, 887, 272, 995, 121, 225, 112, 740, 567, 898, 390, 579, 505, 351, 937,
  825, 323, 874, 138, 512, 671, 297, 179, 277, 304
]
console.log(shortestSeq(big, small))
